The present invention relates to communications systems, and more particularly to synchronization between communicating entities that experience non-controllable delays in an interface between a real-time and a non-realtime layer.
As the number of commonly used computerized, portable devices increases, there is an increased need for communication between these devices. As a result, many standards for providing communication between such devices have been implemented in various data sharing schemes and communication systems.
An example of one such system is called Bluetooth, which has recently been introduced to provide pervasive connectivity especially between portable devices like mobile phones, laptops, personal digital assistants (PDAs), and other nomadic devices. It should be understood that Bluetooth is one of many systems within which the present invention may be employed. Therefore, although some examples of problems to be solved by the present invention will be provided within the context of Bluetooth, those skilled in the art will realize that these examples are merely illustrative, and that the present invention may be employed to solve similar problems within other similar systems.
The Bluetooth system applies frequency hopping to enable the construction of low-power, low-cost radios with a small footprint. The system supports both data and voice. The latter is optimized by applying fast frequency hopping (FH) in combination with a robust voice coding. The fast frequency hopping has a nominal rate of 1600 hops per second (hops/s), corresponding to 800 hops/s in each direction, through the entire 2.4 GHz ISM band, which is 80 MHZ wide.
Devices based on the Bluetooth system concept can create so called piconets, which comprise a master device and one or more slave devices connected via the FH piconet channel. The FH sequence used for the piconet channel is completely determined by the address or identity of the device acting as the master. The system clock of the master device determines the phase in the hopping sequence (i.e., the designation of which one of the possible hops in the sequence is the “current” hop). In the Bluetooth system, each device has a free-running system clock. Each of the slave devices adds a corresponding time offset to its clock that enables it to become aligned with the clock of the master device. By using the master address to select the proper hopping sequence and by using the time offset to align to the master clock, each slave device keeps in hop synchrony to the master device; that is, master and slave devices remain in contact by hopping synchronously to the same hop frequency or hop carrier. For more details, reference is made to U.S. patent application Ser. No. 08/932,911, filed on Sep. 18, 1997 in the name of J. C. Haartsen and entitled “Frequency Hopping Piconets in an Uncoordinated Wireless Multi-user System,” which is hereby incorporated herein by reference in its entirety. Also incorporated by reference herein in its entirety is the Specification of the Bluetooth System, version 1.0A, which is available via the Internet at the following Universal Resource Locator (URL): http://www.bluetooth.com.
As set forth in the Specification of the Bluetooth System, two mechanisms have been included to facilitate low level security functionality: authentication and encryption. The authentication procedure is initiated whenever one unit (denoted herein as “unit A”) wants some proof of the claimed identity of another unit (denoted herein as “unit B”) to which unit A has a Bluetooth radio connection. Once the claimed identities of the involved units have been verified (either single-sided or, if the application that is running over the link so requires, mutually), the units can start using the link for traffic. A prerequisite for a successful authentication is that both units know a common secret, namely, the link key.
The authentication procedure in Bluetooth follows a challenge-response scheme. In short, the verifier generates a challenge in the form of a random number (denoted herein as AU—RAND), that is sent to the claimant. Upon receiving this challenge, the claimant computes a signed response (denoted herein as SRES), that is sent back to the verifier. The verifier can independently compute what the response ought to be (denoted herein as SRES′), given the challenge and the shared secret link key used by the two Bluetooth units. If the received SRES equals the computed SRES′, the authentication is considered successful. If, on the other hand, these two numbers differ, the claimant failed to prove its identity. This challenge-response scheme need not be limited to the Bluetooth system, however, and can be employed in a variety of communications systems requiring authentication. In such systems, a challenge-response format may be used with similar or identical values being communicated between various units of the system.
If the application at some point requires data confidentiality, the units may switch encryption on. This process also requires a common secret: the encryption key. The encryption key is different from, but derived from the link key. Usually, the authentication is done at the time of connection setup. Even if it is possible to repeat the authentication process at later times, it is not mandatory. Therefore, a long time may have elapsed since the authentication was done and the encryption is switched on. Consequently there is no real guarantee that none of the units has been replaced by a malicious user during this time (unless the authentication process is frequently repeated).
Hopefully, as soon as encryption is switched on, a fraudulent unit is immediately disclosed. This is because any such unit should not be in possession of the secret link key that is used by the devices originally involved in the link. Therefore, the unit is also unable to derive the encryption key. To further increase difficulties for a malicious unit, the creation of the encryption key is dependant not only on the link key, but also on a number that is denoted “Authentication Ciphering Offset” (ACO). The ACO is a number that is created for every call of the function that generates the SRES. If two units switch on encryption with different ACOs, their respective generated encryption key will differ even if they use the same link key. More information regarding the use of ACOs may be found in Section 3.2.2 of “Specification of the Bluetooth System, Version 1.2. Core System Package. Part H. November 2003”.
The computation of SRES and ACO is defined by an algorithm that is denoted E1. More formally,E1: {0,1}128×{0,1}128×{0,1}48→{0,1}32×{0,1}96,  (1)(K, AU—RAND, BD—ADDR)(SRES, X)where the notation {0, 1}i denotes a binary number of length i, K is the 128-bit link key, AU—RAND is a 128-bit challenge issued by the verifier, BD—ADDR is the 48-bit Bluetooth device address of the claimant, SRES is a 32-bit signed response, and X is a 96-bit number that is computed at the same time as SRES. It is further noted that the operator “x” does not necessarily represent multiplication, but rather is used to indicate that the parameters to the left of the arrow are applied together in an operation that generates the two parameters to the right of the arrow. This function is defined in Chapter 14 of the Specification of the Bluetooth System. It will be understood, however, by those skilled in the art that other suitable algorithms may be employed, either in the Bluetooth system, or other communication systems.
Currently, for each call of E1, each device updates its value of ACO. Thus, in conventional systems,ACO=X.  (2)
A problem arises in current authentication schemes from the difficulty in synchronizing ACO values. For example, problems may arise from the fact that the current Bluetooth baseband specification says that the units shall always use the latest generated ACO, which may be difficult to ascertain. There are two logical levels of interest to this problem. First, there may be an unknown delay in communications between units. Second, there may be difficulty in determining which transmissions are the latest due to simultaneous or nearly simultaneous transmissions.
FIG. 1 illustrates one possible communications scheme in which authentication and/or encryption may be required between two units. FIG. 1 may relate to the Bluetooth system, or to any other suitable communications system in which authentication and/or encryption are required. As illustrated in FIG. 1, within each unit a Link Manager (LM) 101 generates LM messages, and a Baseband (BB) transmitter 103 executes the actual encoding and transmission of the messages to a BB receiver 105 in the other unit. Likewise, a BB receiver 105 within each unit decodes received bit-streams, and passes these on to the link manager 101 in the layer above. The link manager 101 handles the actual interpretation of the messages.
Unfortunately, due to implementation issues, there may be an unknown delay between the time at which the link manager 101 generates a message and the time at which the BB transmitter 103 transmits that message. The same is true at the receiver side as well: the BB receiver 105 receives a message which is interpreted and handled by the link manager 101 with some unpredictable delay. The above-described situation is true for all sorts of LM messages, including authentication requests within various authentication schemes.
There are several possible reasons for the delay. Clearly, internal hardware design (such as buffering) and the offered traffic load affect this delay. Moreover, the characteristics of the radio channel (such as the interference situation and the signal-to-noise ratio) have an impact. For instance, unit A may have a backlog of messages that have not been delivered yet to unit B because of a bad radio channel. If the link manager 101 in unit A generates a new message, it will be placed in a transmission queue, but it will not be transmitted until all backlogged messages have been sent.
A problem may arise if both units start requesting an authentication of the other side simultaneously (or, to be more precise, within a “short” interval that depends on the actual delay). This is because there is no way to know the length of the delay from the point in time at which an event is generated at one side until the subsequent point in time that the event is registered at the other side. Clearly, in this situation each side needs to call its encryption key generation algorithm E1 two times: once for the request generated by the unit itself, and a second time to generate a response to the request that was received from the other side. As will be illustrated by way of example, due to different delays, the last call at side A may differ from the last call at side B. Consequently, units A and B will generate different encryption keys when encryption is switched on, resulting in their not being able to communicate intelligibly with each other.
FIG. 2 illustrates a case in which both sides end up with the same ACO, resulting in a situation in which they can communicate with one another even after encryption is turned on. The vertical lines represent the time scale of the link manager 101 in each of the units A and B, with time advancing in the downward direction. At step 201, unit A wants to verify the identity of unit B, and so generates a challenge, denoted AU—RANDA. The challenge is transmitted to unit B. At step 203, unit B receives the challenge from unit A, and responds by calling E1 to generate the two parameters SRESA and ACOA. (The subscript A in the various parameters indicates that they are associated with unit A's challenge.) Unit B's generated response parameter, SRESA, is then transmitted back to unit A.
At step 205, unit A receives unit B's response parameter, SRESA, and responds by calling E1 to calculate expected response parameters SRES′A and ACOA. Unit A then can compare the expected signed response, SRES′A with the actual signed response, SRESA, to determine whether unit B is authentic.
At step 207, unit B wants to verify the identity of unit A, and so generates a challenge, denoted AU—RANDB. The challenge is transmitted to unit A. At step 209, unit A receives the challenge from unit B, and responds by calling E1 to generate the two parameters SRESB and ACOB. (The subscript B in the various parameters indicates that they are associated with unit B's challenge.) Unit A's generated response parameter, SRESB, is then transmitted back to unit B.
At step 211, unit B receives unit A's response parameter, SRESB, and responds by calling E1 to calculate expected response parameters SRES′B and ACOB. Unit B then can compare the expected signed response, SRES′B with the actual signed response, SRESB, to determine whether unit A is authentic.
Sometime later, the units decide to utilize encryption in their communication with one another. Accordingly, at step 213, unit A turns on encryption, using its most recently generated value of ACO to generate the encryption key that it will use. Similarly, at step 215, unit B turns on encryption, using its most recently generated value of ACO to generate the encryption key that it will use. In this case, the most recently generated value of ACO at both unit A and unit B is ACOB. Consequently, both units will generate the same encryption key, and will be able to continue communicating with one another.
Turning now to FIG. 3, this illustrates an example in which delays in transmission cause the two units A and B to end up with different ACO values, thereby making it impossible to communicate after encryption is turned on. More specifically, at step 301, unit A wants to verify the identity of unit B, and so generates a challenge, denoted AU—RANDA. The challenge is transmitted to unit B. However at step 303, which is prior to receipt of the challenge from unit A, unit B also decides to verify the identity of unit A, and so generates its own challenge, denoted AU—RANDB.
At step 305, unit A receives unit B's challenge and responds by calling E1 to generate the two parameters SRESB and ACOB. (The subscript B in the various parameters indicates that they are associated with unit B's challenge.) Unit A's generated response parameter, SRESB, is then transmitted back to unit B.
Similarly, at step 307 unit B receives unit A's challenge (transmitted at step 301) and responds by calling E1 to generate the two parameters SRESA and ACOA. (The subscript A in the various parameters indicates that they are associated with unit A's challenge.) Unit B's generated response parameter, SRESA, is then transmitted back to unit A.
At step 309, unit B receives unit A's response parameter, SRESB, and responds by calling E1 to calculate expected response parameters SRES′B and ACOB. Unit B then can compare the expected signed response, SRES′B with the actual signed response, SRESB, to determine whether unit A is authentic.
Similarly, at step 311, unit A receives unit B's response parameter, SRESA, and responds by calling E1 to calculate expected response parameters SRES′A and ACOA. Unit A then can compare the expected signed response, SRES′A with the actual signed response, SRESA, to determine whether unit B is authentic.
Sometime later, the units decide to utilize encryption in their communication with one another. Accordingly, at step 313, unit A turns on encryption, using its most recently generated value of ACO to generate the encryption key that it will use. Similarly, at step 315, unit B turns on encryption, using its most recently generated value of ACO to generate the encryption key that it will use. In this case, the most recently generated value of ACO at unit A is ACOA, whereas the most recently generated value of ACO at unit B is ACO B Consequently, the units A and B will generate different encryption keys, thereby making it impossible to continue communicating with one another.
The problem depicted in FIG. 3 can be averted by using special rules. For example, in the current version of the Bluetooth baseband specification, a solution is provided for by using the following rule:                In case of mutual authentication, the ACO value from the second authentication is retained. However, in some situations an authentication event may be initiated simultaneously in both devices. When this happens, there is no way of telling which is the first and which is the second event. Then, both units shall use the ACO resulting from the challenge generated in the master unit.A second unit (unit B) can determine that an authentication event has been generated simultaneously, or nearly simultaneously, in a first unit (unit A) when a challenge is received from unit A, but a response to a previously sent challenge originating in unit B is expected. In this case, the authentication event initiated by unit B is considered to be open. An authentication event is considered to be open by the originating side until the response has been received. The event is closed when the response has been received and processed by the originating side. Therefore, in a situation similar to the one in FIG. 3, using the Bluetooth rule stated above, unit B would observe that it had received an authentication request at step 307 rather than the expected response to the previously sent challenge, sent at step 303. Therefore, because the request initiated at unit B in step 303 is considered open, ACOA resulting from the challenge generated by the master unit A at step 301 will be used by unit B, rather than ACOB. Likewise, unit A would also receive an authentication request (step 305) while its authentication event initiated at step 301 was open and would therefore also use ACOA according to the same rule. By use of this rule, devices communicating in a Bluetooth system would therefore avert the problem shown in FIG. 3.        
Turning now to FIG. 4, this illustrates an example in which delays in a Bluetooth system, either in transmission or processing, cause the two units A and B to end up with different ACO values, thereby making it impossible to communicate after encryption is turned on. Thus, despite the rule which facilitates communication in a situation like the one depicted in FIG. 3, delays could cause difficulty in communication in a Bluetooth system that uses the same rule. More specifically, at step 401, unit A wants to verify the identity of unit B, and so generates a challenge, denoted AU—RANDA. The challenge is transmitted to unit B. However at step 403, which is prior to receipt of the challenge from unit A, unit B also decides to verify the identity of unit A, and so generates its own challenge, denoted AU—RANDB.
At step 405, unit B receives unit A's challenge (transmitted at step 401) and responds by calling E1 to generate the two parameters SRESA and ACOA. (The subscript A in the various parameters indicates that they are associated with unit A's challenge.) Unit B's generated response parameter, SRESA, is then transmitted back to unit A. Unit B generates this response knowing that its authentication request is open, and it will therefore use the ACO value generated by the master, unit A, according to the Bluetooth specification rule.
At step 407, unit A receives unit B's response parameter, SRESA, at a time denoted tA, and responds by calling E1 to calculate expected response parameters SRES′A and ACOA. Unit A then can compare the expected signed response, SRES′A with the actual signed response, SRESA, to determine whether unit B is authentic. Unit A performs this calculation without knowing that nearly simultaneous verification events have taken place because unit B's request is received after its response to unit A's request, when unit A's authentication event is already closed.
At step 409, unit A receives unit B's challenge and responds by calling E1 to generate the two parameters SRESB and ACOB. (The subscript B in the various parameters indicates that they are associated with unit B's challenge.) Unit A's generated response parameter, SRESB, is then transmitted back to unit B.
At step 411, unit B receives unit A's response parameter, SRES B, at a time denoted tB. However, rather than calling E1 to calculate expected response parameters SRES′B and ACOB, unit B calculates SRES′B but retains ACOA from the master unit A in accordance with the rule of the Bluetooth specification.
The problem illustrated in FIG. 4 arises because the authentication request from unit B AU—RANDB, generated at step 403 by unit B, is received by unit A (step 409) after receipt of the signed response SRESA, which is generated at step 405 by unit B and received at time tA at step 407 by unit A. Consequently, unit A does not know that the two authentication requests have been generated nearly simultaneously because unit A's authentication request event is closed at time tA before the authentication request generated by unit B is received. Therefore, unit A does not apply the Bluetooth specification rule that requires both units to use the master's ACO value, but instead uses ACOB. However, unit B receives unit A's authentication request, which is generated by unit A at step 401 and received by unit B at step 405 after unit B has generated its authentication request at step 403. Because the authentication request generated by unit A is received after the authentication request generated by unit B but before a response is received from unit A at step 411, unit B realizes that the two authentication requests are nearly simultaneous, and applies the Bluetooth specification rule which requires unit B to use the ACO value of the master unit, or ACOA.
As a consequence of this time delay of unit B's authentication request, when the two devices later turn on encryption, unit A utilizes ACOB, as shown at step 413, and unit B utilizes ACOA, as shown at step 415. As a consequence, once encryption is turned on by the two units using different ACO values, communication will be impossible.
In the examples described above, it was assumed that each unit generates its expected signed response, SRES′, only after receiving the actual signed response from the other unit. However, this is not a requirement, as a unit could, for example, generate its expected signed result (SRES′) at the same time that it generates the challenge, AU—RAND. Such a determination of when an SRES′ is generated may be dependent on the system in which it is being implemented. The Specification of the Bluetooth System, for example, leaves the particular implementation up to the developer. Because there is no requirement that it be done one way or the other, it is possible that one unit, made by a first manufacturer, will compute SRES′ at the same time that it generates the challenge, while the other unit, made by a different manufacturer, will generate its SRES′ only upon receiving the signed response from the other side. In such a scenario, the two units could again end up with different most-recently-generated values of ACO, which makes it impossible for them to generate the same encryption key when encryption is turned on.
There is therefore, a need for a system that avoids the problems associated with the prior art, such as the possibility of ending up with different ACO values, and thereby using incompatible encryption.